﻿#define _CRT_SECURE_NO_WARNINGS
/*你有一个背包，最多能容纳的体积是V。

现在有n种物品，每种物品有任意多个，第i种物品的体积为
​
（1）求这个背包至多能装多大价值的物品？
（2）若背包恰好装满，求至多能装多大价值的物品？*/

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, V;
    cin >> n >> V;
    vector<int> v(n), w(n);
    for (int i = 0; i < n; i++)
        cin >> v[i] >> w[i];

    vector<vector<int>> dp1(n + 1, vector<int>(V + 1, 0));
    auto dp2 = dp1;

    for (int j = 1; j <= V; j++)    dp2[0][j] = -1;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= V; j++)
        {
            dp1[i][j] = dp1[i - 1][j];
            dp2[i][j] = dp2[i - 1][j];
            if (j >= v[i - 1])
            {
                dp1[i][j] = max(dp1[i][j], dp1[i][j - v[i - 1]] + w[i - 1]);
                if (dp2[i][j - v[i - 1]] != -1)
                {
                    dp2[i][j] = max(dp2[i][j], dp2[i][j - v[i - 1]] + w[i - 1]);
                }
            }
        }
    }

    cout << dp1[n][V] << endl;
    if (dp2[n][V] == -1)
        cout << 0;
    else cout << dp2[n][V];
}
// 64 位输出请用 printf("%lld")


/*给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。*/

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        const int INF = 0x3f3f3f3f;
        vector<vector<int>> dp(n + 1, vector<int>(amount + 1, 0));
        for (int j = 1; j <= amount; j++)
        {
            dp[0][j] = INF;
        }

        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j <= amount; j++)
            {
                dp[i][j] = dp[i - 1][j];
                if (j >= coins[i - 1])
                {
                    dp[i][j] = min(dp[i][j], dp[i][j - coins[i - 1]] + 1);
                }
            }
        }

        return dp[n][amount] == INF ? -1 : dp[n][amount];
    }
};

/*给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。 

题目数据保证结果符合 32 位带符号整数。*/

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();

        vector<vector<int>> dp(n + 1, vector<int>(amount + 1, 0));

        for (int j = 1; j <= amount; j++)   dp[0][j] = 0;
        dp[0][0] = 1;

        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j <= amount; j++)
            {
                dp[i][j] += dp[i - 1][j];
                if (j >= coins[i - 1] && dp[i][j - coins[i - 1]] != -1)
                {
                    dp[i][j] += dp[i][j - coins[i - 1]];
                }
            }
        }
        for (int i = 0; i <= n; i++)
        {
            for (int j = 0; j <= amount; j++)
            {
                cout << dp[i][j] << " ";
            }
            cout << endl;
        }
        return dp[n][amount] == -1 ? 0 : dp[n][amount];
    }
};

/*给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。
例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是*/

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1);
        dp[1] = 1;
        for (int i = 2; i <= n; i++)
        {
            dp[i] = 1 + dp[i - 1];
            for (int j = 2; j * j <= i; j++)
            {
                dp[i] = min(dp[i], dp[i - j * j] + 1);
            }
        }

        return dp[n];
    }
};